package fun.ticsmyc.dataStructure;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question
 * @date 2020-02-23 12:34
 *
 * 前缀树的  插入、 删除 、 查找、 前缀匹配
 *
 */
public class 前缀树 {

    public static class TrieNode{
        int path;
        int end;
        TrieNode[] next;
        public TrieNode(){
            path=0;
            end=0;
            next=new TrieNode[26];
        }
    }

    public static class Trie{
        private TrieNode root;
        public Trie(){
            root=new TrieNode();
        }

        /**
         * 插入
         * @param word
         */
        public void insert(String word) {
            if(word == null){
                return;
            }
            TrieNode cur =root;
            char[] chs = word.toCharArray();
            for(int i =0 ; i<chs.length;++i){
                if(cur.next[chs[i]-'a'] == null){
                    cur.next[chs[i]-'a'] = new TrieNode();
                }
                cur=cur.next[chs[i]-'a'];
                cur.path++;
            }
            cur.end++;
        }

        /**
         * 查找前缀树中有几个word
         * @param word
         * @return
         */
        public int search(String word){
            if(word == null){
                return 0;
            }
            char[] chs = word.toCharArray();

            TrieNode node =root;
            for(int i=0 ; i< chs.length; ++i){
                if(node.next[chs[i]-'a'] != null){
                    node=node.next[chs[i]-'a'];
                }else{
                    return 0;
                }
            }
            return node.end;
        }

        /**
         * 删除
         * @param word
         */
        public void delete(String word){
            if(search(word) != 0 ){
                char[] chs = word.toCharArray();
                TrieNode node = root;
                for(int i=0 ; i<chs.length;++i){
                    TrieNode next  = node.next[chs[i]-'a'];
                    if(next.path==1){
                        node.next[chs[i]-'a']=null;
                        return;
                    }else{
                        next.path--;
                    }
                    node=next;
                }
                node.end--;
            }
        }

        /**
         * 前缀数量统计
         * @param pre
         * @return
         */
        public int prefixNumber(String pre) {
            if(pre == null){
                return 0;
            }
            char[] chs =pre.toCharArray();
            TrieNode node =root;
            for(int i=0;i<chs.length;++i){
                if(node.next[chs[i]-'a'] != null){
                    node=node.next[chs[i]-'a'];
                }else{
                    return 0;
                }
            }
            return node.path;
        }

        public static void main(String[] args) {
            Trie trie = new Trie();
            System.out.println(trie.search("zuo"));
            trie.insert("zuo");
            System.out.println(trie.search("zuo"));
            trie.delete("zuo");
            System.out.println(trie.search("zuo"));
            trie.insert("zuo");
            trie.insert("zuo");
            trie.delete("zuo");
            System.out.println(trie.search("zuo"));
            trie.delete("zuo");
            System.out.println(trie.search("zuo"));
            trie.insert("zuoa");
            trie.insert("zuoac");
            trie.insert("zuoab");
            trie.insert("zuoad");
            trie.delete("zuoa");
            System.out.println(trie.search("zuoa"));
            System.out.println(trie.prefixNumber("zuo"));
        }
    }
}
